package main.leetcode.offer.firstround.from51to68;

/**
 * 58-I.翻转单词顺序
 *
 * <p>输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a
 * am I"。
 *
 * <p>
 *
 * <p>示例 1：输入: "the sky is blue" 输出: "blue is sky the"
 *
 * <p>示例 2：输入: "  hello world!  " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *
 * <p>示例 3：输入: "a good   example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * <p>说明：无空格字符构成一个单词。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex58I {
    public static void main(String[] args) {
        System.out.println(new ex58I().reverseWords("  hello world!  "));
        System.out.println(new ex58I().reverseWords("the sky is blue"));
        System.out.println(new ex58I().reverseWords("  "));
        System.out.println(new ex58I().reverseWords(" a"));
    }

    public String reverseWords(String s) {
        int n = s.length();
        if (n < 1) return s;
        StringBuilder res = new StringBuilder();
        int tail = n;
        for (int i = n - 2; i >= 0; --i) {
            // 对应字符+空格，改变尾指针
            if (s.charAt(i) != ' ' && s.charAt(i + 1) == ' ') {
                tail = i + 1;
            }
            // 对应空格+字符，连接单词
            if (s.charAt(i) == ' ' && s.charAt(i + 1) != ' ') {
                res.append(' ').append(s, i + 1, tail);
            }
        }
        if (tail == n && s.charAt(tail - 1) == ' ') return ""; // 全为空格 或 全为字符 的情况要单独判断，前者需直接返回""
        // 排在原字符串最开始的，若是单词，则另外连接
        if (s.charAt(0) != ' ') res.append(' ').append(s, 0, tail);
        // 删除连接进来的首空格
        res.deleteCharAt(0);
        return res.toString();
    }
}
